Applications of sketches in network traffic measurement: A survey

Accurate and timely network traffic measurement is essential for network status monitoring, network fault analysis, network intrusion detection, and network security management. With the rapid development of the network, massive network traffic brings severe challenges to network traffic measurement. However, existing measurement methods suffer from many limitations for effectively recording and accurately analyzing big-volume traffic. Recently, sketches, a family of probabilistic data structures that employ hashing technology for summarizing traffic data, have been widely used to solve these problems. However, current literature still lacks a thorough review on sketch-based traffic measurement methods to offer a comprehensive insight on how to apply sketches for fulfilling various traffic measurement tasks. In this paper, we provide a detailed and comprehensive review on the applications of sketches in network traffic measurement. To this end, we classify the network traffic measurement tasks into four categories based on the target of traffic measurement, namely cardinality estimation, flow size estimation, change anomaly detection, and persistent spreader identification. First, we briefly introduce these four types of traffic measurement tasks and discuss the advantages of applying sketches. Then, we propose a series of requirements with regard to the applications of sketches in network traffic measurement. After that, we perform a fine-grained classification for each sketch-based measurement category according to the technologies applied on sketches. During the review, we evaluate the performance, advantages and disadvantages of current sketch-based traffic measurement methods based on the proposed requirements. Through the thorough review, we gain a number of valuable implications that can guide us to choose and design proper traffic measurement methods based on sketches. We also review a number of general sketches that are highly expected in modern network systems to simultaneously perform multiple traffic measurement tasks and discuss their performance based on the proposed requirements. Finally, through our serious review, we summarize a number of open issues and identify several promising research directions.     

A study on the monitoring model development for quality measurement of internet traffic

The recent trend of integration among new network services such as the long-term evolution (LTE) based on internet protocol (IP) needs reputable analyses and prediction information on the internet traffic. The IP along with increased internet traffics due to expanding new service platforms such as smartphones will reflect policies such as network QoS according to new services. The establishment of monitoring methods and analysis plans is thus required for the development of internet traffics that will analyze their status and predict their future. The paper with the speed of Internet traffic model is developed for monitoring the state of the experiment and verified. The problem is that the proposed service Internet service provider (ISP) to resolve the conflict between the occurrences can be considerably Internet traffic and that the state of data may be helpful in understanding. The paper advancement policy to reflect the network traffic volume of Internet services and users irradiation with increased traffic due to the development and management of the analysis was carried out experimental measurements.     

Revisiting the Parallel Strategy for DOACROSS Loops

Journal of Computer Science and Technology - DOACROSS loops are significant parts in many important scientific and engineering applications, which are generally exploited pipeline/wave-front...     

Profiling drunk driving recidivists in Denmark

Drunk drivers are a menace to themselves and to other road users, as drunk driving significantly increases the risk of involvement in road accidents and the probability of severe or fatal injuries. Although injuries and fatalities related to road accidents have decreased in recent decades, the prevalence of drunk driving among drivers killed in road accidents has remained stable, at around 25% or more during the past 10 years. Understanding drunk driving, and in particular, recidivism, is essential for designing effective countermeasures, and accordingly, the present study aims at identifying the differences between non-drunk drivers, drunk driving non-recidivists and drunk driving recidivists with respect to their demographic and socio-economic characteristics, road accident involvement and other traffic and non-traffic-related law violations. This study is based on register-data from Statistics Denmark and includes information from 2008 to 2012 for the entire population, aged 18 or older, of Denmark. The results from univariate and multivariate statistical analyses reveal a five year prevalence of 17% for drunk driving recidivism, and a significant relation between recidivism and the drunk drivers’ gender, age, income, education, receipt of an early retirement pension, household type, and residential area. Moreover, recidivists are found to have a higher involvement in alcohol-related road accidents, as well as other traffic and, in particular, non-traffic-related offences. These findings indicate that drunk driving recidivism is more likely to occur among persons who are in situations of socio-economic disadvantage and marginalisation. Thus, to increase their effectiveness, preventive measures aiming to reduce drunk driving should also address issues related to the general life situations of the drunk driving recidivists that contribute to an increased risk of drunk driving recidivism.     

Survey on Passivity Based Control of Induction Machine

Induction machines (IM) constitute a theoretically interesting and practically important class of nonlinear systems. They are frequently used as wind generators for their power/cost ratio. They are described by a fifth‐order nonlinear differential equation with two inputs and only three state variables available for measurement. The control task is further complicated by the fact that IM are subject to unknown (load) disturbances and the parameters can be of great uncertainty. One is then faced with the challenging problem of controlling a highly nonlinear system, with unknown time‐varying parameters, where the regulated output, besides being unmeasurable, is perturbed by an unknown additive signal. Passivity‐based control (PBC) is a well‐established structure‐preserving design methodology which has shown to be very powerful to design robust controllers for physical systems described by Euler‐Lagrange equations of motion. PBCs provide a natural procedure to "shape" the potential energy yielding controllers with a clear physical interpretation in terms of interconnection of the system with its environment and are robust vis á vis to unmodeled dissipative effects. One recent approach of PBC is the Interconnection and Damping Assignment Passivity‐Based Control (IDA‐PBC) which is a very useful technique to control nonlinear systems assigning a desired (Port‐Controlled Hamiltonian) structure to the closed‐loop. The aim of this paper is to give a survey on different PBC of IM. The originality of this work is that the author proves that the well known field oriented control of IM is a particular case of the IDA‐PBC with disturbance.     

Frequency Insertion Strategy for Channel Assignment Problem

This paper presents a new heuristic method for quickly finding a good feasible solution to the channel assignment problem (CAP). Like many other greedy-type heuristics for CAP, the proposed method also assigns a frequency to a call, one at a time. Hence, the method requires computational time that increases only linear to the number of calls. However, what distinguishes the method from others is that it starts with a narrow enough frequency band so as to provoke violations of constraints that we need to comply with in order to avoid radio interference. Each violation is then resolved by inserting frequencies at the most appropriate positions so that the band of frequencies expands minimally. An extensive computational experiment using a set of randomly generated problems as well as the Philadelphia benchmark instances shows that the proposed method perform statistically better than existing methods of its kind and even yields optimum solutions to most of Philadelphia benchmark instances among which two cases are reported for the first time ever, in this paper. Won-Young Shin was born in Busan, Korea in 1978. He received B.S. in industrial engineering from Pohang University of Science and Technology (POSTECH) in 2001 and M.S in operation research and applied statistics from POSTECH in 2003. Since 2003 he has been a researcher of Agency for Defense Development (ADD) in Korea. He is interested in optimization of communication system and applied statistics. Soo Y. Chang is an associate professor in the Department of Industrial Engineering at Pohang University of Science and Technology (POSTECH), Pohang, Korea. He teaches linear programming, discrete optimization, network flows and operations research courses. His research interests include mathematical programming and scheduling. He has published in several journals including Discrete Applied Mathematics, Computers and Mathematics with Application, IIE Transactions, International Journal of Production Research, and so on. He is a member of Korean IIE, and ORMSS. Jaewook Lee is an assistant professor in the Department of Industrial Engineering at Pohang University of Science and Technology (POSTECH), Pohang, Korea. He received the B.S. degree in mathematics with honors from Seoul National University, and the Ph.D. degree from Cornell University in applied mathematics in 1993 and 1999, respectively. He is currently an assistant professor in the department of industrial engineering at the Pohang University of Science and Technology (POSTECH). His research interests include nonlinear systems, neural networks, nonlinear optimization, and their applications to data mining and financial engineering. Chi-Hyuck Jun was born in Seoul, Korea in 1954. He received B.S. in mineral and petroleum engineering from Seoul National University in 1977, M.S. in industrial engineering from Korea Advanced Institute of Science and Technology in 1979 and Ph.D. in operations research from University of California, Berkeley, in 1986. Since 1987 he has been with the department of industrial engineering, Pohang University of Science and Technology (POSTECH) and he is now a professor and the department head. He is interested in performance analysis of communication and production systems. He has published in several journals including IIE Transactions, IEEE Transactions, Queueing Systems and Chemometrics and Intelligent Laboratory Systems. He is a member of IEEE, INFORMS and ASQ.     

新一代IP QoS的实现

文章介绍了新一代IP骨干网上的IP QoS实现技术，论述了集成业务(IntServ)与差分业务(DiffServ)解决方案的特点，详细介绍了相关的队列管理与排队机制。并结合多协议标签交换（MPLS)技术的最新发展，阐述了综合多协议标签交换流量工程与DiffServ技术体系端到端IP QoS的实现。     

Fast handoff with reducing waste rate approach for wireless resources management in UMTS mobile networks

3G Wideband CDMA systems adopt the Orthogonal Variable Spreading Factor code tree as the channelization codes management for achieving high data rate transmission in personal multimedia communications. It assigns a single channelization code for each accepted connection. Nevertheless, it wastes the system capacity when the required rate is not powers of two of the basic rate. One good solution is to assign multiple codes for each accepted connection but it causes two inevitable drawbacks: long handoff delay and new call setup delay due to high complexity of processing with multiple channelization codes, and high cost of using more number of rake combiners. Especially, long handoff delay may result in more call dropping probability and higher Grade of Service, which will degrade significantly the utilization and revenue of the 3G cellular systems. Therefore, we propose herein an adaptive efficient codes determination algorithm based on the Markov Decision Process analysis approach to reduce the waste rate and reassignments significantly while providing fast handoff. Numerical results demonstrate that the proposed approach yields several advantages, including the lowest GOS, the least waste rate, and the least number of reassignments. Meanwhile, the optimal number of rake combiners is also analyzed in this paper. This research was supported in part by the National Science Council of Taiwan, ROC, under contract NSC-93-2213-E-324-018.     

Range Assignment for Biconnectivity and k-Edge Connectivity in Wireless Ad Hoc Networks

Depending on whether bidirectional links or unidirectional links are used for communications, the network topology under a given range assignment is either an undirected graph referred to as the bidirectional topology, or a directed graph referred to as the unidirectional topology. The Min-Power Bidirectional (resp., Unidirectional) k-Node Connectivity problem seeks a range assignment of minimum total power subject to the constraint that the produced bidirectional (resp. unidirectional) topology is k-vertex connected. Similarly, the Min-Power Bidirectional (resp., Unidirectional) k-Edge Connectivity problem seeks a range assignment of minimum total power subject to the constraint the produced bidirectional (resp., unidirectional) topology is k-edge connected. The Min-Power Bidirectional Biconnectivity problem and the Min-Power Bidirectional Edge-Biconnectivity problem have been studied by Lloyd et al. [23]. They show that range assignment based the approximation algorithm of Khuller and Raghavachari [18], which we refer to as Algorithm KR, has an approximation ratio of at most 2(2 – 2/n)(2 + 1/n) for Min-Power Bidirectional Biconnectivity, and range assignment based on the approximation algorithm of Khuller and Vishkin [19], which we refer to as Algorithm KV, has an approximation ratio of at most 8(1 – 1/n) for Min-Power Bidirectional Edge-Biconnectivity. In this paper, we first establish the NP-hardness of Min-Power Bidirectional (Edge-) Biconnectivity. Then we show that Algorithm KR has an approximation ratio of at most 4 for both Min-Power Bidirectional Biconnectivity and Min-Power Unidirectional Biconnectivity, and Algorithm KV has an approximation ratio of at most 2k for both Min-Power Bidirectional k-Edge Connectivity and Min-Power Unidirectional k-Edge Connectivity. We also propose a new simple constant-approximation algorithm for both Min-Power Bidirectional Biconnectivity and Min-Power Unidirectional Biconnectivity. This new algorithm applies only to Euclidean instances, but is best suited for distributed implementation. A preliminary version of this work appeared in the proceedings of the 2nd International Conference on AD-HOC Network and Wireless (Adhoc-Now 2003). Research performed in part while visiting the Max-Plank-Institut fur Informatik. Gruia Calinescu is an Assistant Professor of Computer Science at the Illinois Institute of Technology since 2000. He held postdoc or visiting researcher positions at DIMACS, University of Waterloo, and Max-Plank Institut fur Informatik. Gruia has a Diploma from University of Bucharest and a Ph.D. from Georgia Insitute of Technology. His research interests are in the area of algorithms. Peng-Jun Wan has joined the Computer Science Department at Illinois Institute of Technology in 1997 and has been an Associate Professor since 2004. He received his Ph.D. in Computer Science from University of Minnesota in 1997, M.S. in Operations Research and Control Theory from Chinese Academy of Science in 1993, and B.S. in Applied Mathematics from Tsinghua University in 1990. His research interests include optical networks and wireless networks.     

Analysis of Distributed DDQ for QoS Router

In a packet switching network, congestion is unavoidable and affects the quality of real‐time traffic with such problems as delay and packet loss. Packet fair queuing (PFQ) algorithms are well‐known solutions for quality‐of‐service (QoS) guarantee by packet scheduling. Our approach is different from previous algorithms in that it uses hardware time achieved by sampling a counter triggered by a periodic clock signal. This clock signal can be provided to all the modules of a routing system to get synchronization. In this architecture, a variant of the PFQ algorithm, called digitized delay queuing (DDQ), can be distributed on many line interface modules. We derive the delay bounds in a single processor system and in a distributed architecture. The definition of traffic contribution improves the simplicity of the mathematical models. The effect of different time between modules in a distributed architecture is the key idea for understanding the delay behavior of a routing system. The number of bins required for the DDQ algorithm is also derived to make the system configuration clear. The analytical models developed in this paper form the basis of improvement and application to a combined input and output queuing (CIOQ) router architecture for a higher speed QoS network.